
"""
654. 最大二叉树
"""
import sys
from typing import Optional, List

from com.siyuan.TreeNode import TreeNode


class Solution:

    """
    分解二叉树
    定义函数：每次先找到最大值，再分别构建左右子树
    """
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        return self.build(nums, 0, len(nums) - 1)

    '''遍历二叉树'''
    def build(self, nums, i, j) -> Optional[TreeNode]:
        if i > j:
            return None

        # 找到最大值
        index = -1
        max_val = -sys.maxsize - 1
        for k in range(i, j + 1):
            if nums[k] > max_val:
                max_val = nums[k]
                index = k
        root = TreeNode(max_val)

        # 前序位置
        root.left = self.build(nums, i, index - 1)
        # 中序位置
        root.right = self.build(nums, index + 1, j)
        # 后序位置
        return root


if __name__ == '__main__':
    print(-sys.maxsize - 1)